#
# @lc app=leetcode.cn id=145 lang=python3
#
# [145] 二叉树的后序遍历
#
# https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/
#
# algorithms
# Easy (75.35%)
# Likes:    750
# Dislikes: 0
# Total Accepted:    359.1K
# Total Submissions: 476.6K
# Testcase Example:  '[1,null,2,3]'
#
# 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
# 
# 
# 
# 示例 1：
# 
# 
# 输入：root = [1,null,2,3]
# 输出：[3,2,1]
# 
# 
# 示例 2：
# 
# 
# 输入：root = []
# 输出：[]
# 
# 
# 示例 3：
# 
# 
# 输入：root = [1]
# 输出：[1]
# 
# 
# 
# 
# 提示：
# 
# 
# 树中节点的数目在范围 [0, 100] 内
# -100 <= Node.val <= 100
# 
# 
# 
# 
# 进阶：递归算法很简单，你可以通过迭代算法完成吗？
# 
#
# %%
from typing import Optional
from typing import List
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
# @lc code=start
# Definition for a binary tree node.
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        postorder_list = []
        system_stack = []
        if root:
            system_stack.append(root)
            while system_stack:
                current = system_stack[-1]
                if current.left:
                    system_stack.append(current.left)
                    current.left = None
                    continue
                if current.right:
                    system_stack.append(current.right)
                    current.right = None
                    continue
                postorder_list.append(system_stack.pop().val)
        return postorder_list
# @lc code=end

# %%
treenode = []
for i in [1,None,2,3]:
    if i is not None:
        treenode.append(TreeNode(i))
    else:
        treenode.append(None)
for j, node in enumerate(treenode):
    if node is not None and j + 1 < len(treenode):
        node.left = treenode[j + 1]
    if node is not None and j + 2 < len(treenode):
        node.right = treenode[j + 2]
solution = Solution()
solution.postorderTraversal(treenode[0])